This application is being filed with a microfiche appendix consisting of 111 frames on 2 sheets containing source code listings for software components related to the invention. Appendix sections are labeled A, B, D, and E.
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
The present invention is related to the field of digital circuits and to the field of instructions and program code for the operation thereof. More particularly, the present invention is related to data communication between digital circuits or between processes running on the same circuit. The invention is further related to fault-tolerant and scalable distributed processor and distributed memory digital processing systems.
This discussion of the present invention presupposes some familiarity with computer programming and software, particularly data input and output (I/O), network communications, and interprocess communications. The present invention also presupposes some familiarity with multiprocessor and nonshared memory computer systems, as discussed in co-assigned U.S. Pat. No. 4,228,496, which is incorporated herein by reference to the extent necessary to understand and enable the invention. This discussion of the present invention also presupposes some familiarity with the UNIX and related operating systems and with the well-known sockets protocol for enabling interprocess and network communication.
In all cases, the glossary and specific examples given herein are intended to be illustrative of the invention but not limiting. It will be apparent to anyone of skill in the art that the present invention may be implemented in an unlimited variety of operating system environments. Therefore, the invention should not be limited except as provided in the attached claims.
Background of Select( ) and Sockets( )
In UNIX and other operating systems (OS""s), processes use a select( ) (or a similar) system call to inform the OS kernel that they are interested in a particular resource for interprocess communication. A simple example would be a process that needs to wait for a particular resource to have data to read or to be available for a write. Rather than the process using CPU time to repeatedly query the connection to determine if the connection is ready, the process may call select( ) and then become dormant if the connection is not immediately ready. The call to select( ) registers with the OS kernel that the calling process needs to be awakened when the interprocess communication resource becomes ready.
The select( ) OS call may be used by a process having open connections to one or more sockets. A socket is a resource for interprocess communication that is generally used between a user process and a special I/O process handling a network I/O protocol such as the common internet protocols TCP or IP. Sockets are generally implemented as a data structure within the OS memory space, and this memory space is accessible to the OS, the I/O process responsible for delivering data to the socket, and the user process that is communicating via the socket. A socket data structure has associated with it all state information necessary to handle the interprocess communication and generally includes a pointer to a memory location for temporarily storing the actual data packets flowing between the user process and the I/O connection.
Select( ) also may be used on other OS data structures used for interprocess communication such as pipes or FIFOs and for other opened I/O such as ttys, disk opens, and directory opens. While select( ) performs a similar function no matter what type of data structure it is called on, the details of the select( ) implementation for different data structures may vary in different operating systems as described more fully below.
A good description of the select( ) system call and sockets can be found in the reference book UNIX Network Programming, by Richard Stevens, (section 6.13), Prentice Hall, 1990.
Background of Distributed Memory Environments
In operating systems that have a single central processing unit (CPU) or multiple CPUs with shared memory, select( ) can be easily implemented because the data structures representing sockets, pipes, or FIFOs in the system are contained in a single memory space, as shown in FIG. 1, and therefore can be directly accessible to every process running in that memory space, including the OS.
However, in non-shared memory distributed systems, such as that discussed in U.S. Pat. No. 4,228,496, select( ) is more difficult to implement because the information regarding the occurrence of different events on different data structures may be contained in a memory different from that which holds the user process calling select and may not be directly accessible even to the OS local to the process that called select.
What is needed is a method for performing a select( ) function effectively in a distributed memory environment.
Glossary
The following terms are used in this application in accordance with the explanations below and also in accordance with their broad meanings as understood in the art.
Connectionxe2x80x94a means for communicating data between processes or between a process and an I/O device, such as a socket, a RAM file, a disk file, a directory, a pipe, a FIFO, a TTY, etc.
Eventxe2x80x94an occurrence on a connection, such as a ready-to-read, ready-to-write, or exceptional condition.
File descriptor (FD)xe2x80x94An identifier local to a user process and shared by only that process and related (child) processes for identifying a particular connection opened or created by that process.
I/O processxe2x80x94An input/output process for managing data input and output on some physical resources such as a network. Also called a server process.
Kernelxe2x80x94The executing operating system executable code that manages the activity of all other processes.
Messagexe2x80x94In a distributed CPU environment, data communicated between two or more different CPUs or memory spaces over a communications channel.
Operating System (OS)xe2x80x94The kernel and other callable functions and resources available to processes.
Processxe2x80x94a collection (generally a sequence) of executable program code and associated state information that can independently execute and may at any given time be either executing or dormant.
Socketxe2x80x94A data construct residing in a memory that allows one process to communicate data with another process via a standard interface.
User processxe2x80x94A process created to perform a user function. Also called an application.